
// Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution
{
public:
    // 找中点分离链表 + 反转链表 + 合并链表
    ListNode *detach_List(ListNode *head)
    {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *ret = slow->next;
        slow->next = nullptr;
        return ret;
    }
    ListNode *reverseList(ListNode *head)
    {
        ListNode *pev = nullptr;
        ListNode *cur = head;
        while (cur)
        {
            ListNode *next = cur->next;
            cur->next = pev;
            pev = cur;
            cur = next;
        }
        return pev;
    }
    void merge_List(ListNode *l1, ListNode *l2)
    {
        while (l1 && l2)
        {
            ListNode *l1_next = l1->next;
            ListNode *l2_next = l2->next;
            l2->next = l1->next;
            l1->next = l2;
            if (!l1_next)
            {
                l1->next = l2_next;
            }
            l1 = l1_next;
            l2 = l2_next;
        }
    }
    void reorderList(ListNode *head)
    {
        merge_List(head, reverseList(detach_List(head)));
    }
};
// #include <iostream>
// #include <vector>
// using namespace std;
// class Solution
// {
// public:
//     // 空间换时间O(N) 相撞指针O(N)
//     void reorderList(ListNode *head)
//     {
//         vector<ListNode *> vt;
//         while (head)
//         {
//             vt.push_back(head);
//             head = head->next;
//         }
//         int i = 0, j = vt.size() - 1;
//         while (i < j)
//         {
//             vt[j]->next = vt[i]->next;
//             vt[i]->next = vt[j];
//             i++, j--;
//         }
//         vt[i]->next = nullptr;
//     }
// };